package com.richpay.basejava.base14;

/**
 * 插入排序，将a[i]插入到a[0]的前面或后面，
 * 继续这一过程，将a[i]插入到a[i-1]的合适位置。
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] intArray = {15, 23, 8, 10, 7};
        System.out.println("原始数组:");
        print(intArray);

        insertSort(intArray);
        System.out.println("排序后的数组:");
        print(intArray);
    }


    /**
     * @param array 传入一个数组，依次打印数组元素的值
     */
    static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();//换行
    }

    /**
     * 进行插入排序：
     * 15 23 8 10 7
     * 此时0索引的为15已经放入完毕。
     * =============== 第一趟
     * 第一次a[1]和a[0]比较: a[1]=23应放在a[0]=15后面位置。
     * 15 23 8 10 7
     * =============== 第二趟
     * 第一次a[2]和a[1]比较:a[2]=8应该放在a[1]=23前面位置。
     * 15 8 23 10 7
     * 第二次a[1]和a[0]比较:a[1]=8应该放在a[0]=15前面位置。
     * 8 15 23 10 7
     * =============== 第三趟
     * 第一次a[3]和a[2]比较:a[3]=10应该放在a[2]=23的前面位置。
     * 8 15 10 23 7
     * 第二次a[2]和a[1]比较:a[2]=10应该放在a[1]=15的前面位置。
     * 8 10 15 23 7
     * 第三次a[1]和a[0]比较:a[1]=10应该放在a[0]=8的后面位置。
     * 8 10 15 23 7
     * =============== 第四趟
     * 第一次a[4]和a[3]比较:a[4]=7应该放在a[3]=23的前面位置。
     * 8 10 15 7 23
     * 第二次a[3]和a[2]比较:a[3]=7应该放在a[2]=15的前面位置。
     * 8 10 7 15 23
     * 第三次a[2]和a[1]比较:a[2]=7应该放在a[1]=10的前面位置。
     * 8 7 10 15 23
     * 第四次a[1]和a[0]比较:a[1]=7应该放在a[0]=8的前面位置。
     * 7 8 10 15 23
     *
     * @param array
     */
    static void insertSort(int[] array) {
        int len = array.length;
        for (int i = 1; i < len; i++) {
            System.out.println("第" + i + "趟");

            for (int j = i; j > 0; j--) {
                //  System.out.println("第" + (i - j + 1) + "次");

                if (array[j - 1] > array[j]) {
                    System.out.println("执行了置换");

                    swap(array, j - 1, j);
                } else {
                    //  System.out.println("执行了break");
                    // break;
                }
                System.out.println("第" + (i - j + 1) + "次,执行后的数组:");
                print(array);
            }
            System.out.println("第" + i + "趟,执行后的数组:");
            print(array);
        }

    }

    static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}
